package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-03-05 18:59
 */
public class n_11 {
    public static void main(String[] args) {
        int[] arr={3,4,5,1,2};
        n_11 n = new n_11();
        int res = n.minNumberInRotateArray(arr);
        System.out.println(res);
    }

    public int minNumberInRotateArray(int [] array) {
        if (array==null || array.length==0){
            return 0;
        }
        int left =0;
        int right = array.length-1;
        while (left<right){
            int mid = left+(right-left)/2;
            if (array[mid]<=array[right]){
                right=mid;
            }else {
                left=mid+1;
            }
        }
        return array[left];
    }

    /**
     * 如果数组元素允许重复
     * @param array
     * @return
     */
    public int minNumberInRotateArray2(int[] array){
        if (array==null || array.length==0){
            return 0;
        }
        int left =0;
        int right = array.length-1;
        while (left<right){
            int mid = left+(right-left)/2;
            if (array[mid]==array[left]&&array[left]==array[right]){
                getMin(array,left,right);
            }
            if (array[mid]<=array[right]){
                right=mid;
            }else {
                left=mid+1;
            }
        }
        return array[left];
    }

    public int getMin(int[] array,int left,int right){
        while (left<right){
            if (array[left]>array[left+1]){
                return array[left+1];
            }
            left++;
        }
        return array[left];
    }

    public int minNumberInRotateArray3(int [] array) {
        if (array==null||array.length==0){
            return 0;
        }
        int len=array.length;
        int left=0;
        int right = len-1;
        while (left<right){
            int mid=left+(right-left)/2;
            if (array[mid]<array[right]){
                right=mid;
            }else {
                left=mid+1;
            }

        }
        return array[left];
    }
}
